In computer graphics, a rendering program renders an image by producing pixels from a scene description. Scene description input files contain a three dimensional geometric description of all objects in the scene, as well as a virtual-camera description and light descriptions. A shader program may be associated with each object in the scene and tagged to each light to compute shading values for the object. Shading values may be related to properties such as color, shadow, smoke, reflections, texture, and the like.
While rendering an image, the rendering program reads the geometric description of an object and divides the object into smaller subobjects. Object division occurs along parametric lines in a natural, local coordinate system on the object. Object division continues until each individual subobject is essentially “flat” or otherwise small enough to be accurately shaded.
Once a subobject is ready for shading, a series of shading points are defined on the subobject. The data representing each shading point consists of a set of properties. Example properties include the position (P) of the point in space at coordinates (x, y, z), the surface normal (N) at P, and the nominal color (CS) of P. The shader program operates on these values and produces output values at each shading point. The rendering program collects the outputs on all shading points and then samples them, interpolating as necessary, to populate pixels for an output frame buffer.
A shader compiler converts the text of the shader program to an executable form. A shader interpreter reads the executable form and evaluates the instructions on a particular set of shading point values. The shading points from a particular subobject are referred to as a shading grid. The shading grid represents several arrays of input values for shader instructions. For example, N values can be collected from all shading points and an operation can be performed on all of the N values at the same time. Thus, shader operators can function in an single instruction, multiple data (SIMD) fashion before the interpreter evaluates the next operator.
In some embodiments of a shading system, there may be several available ray tracing functions which may be implemented directly as individual operators or as expressions of several operators. Examples may include trace( ), gather( ), environment( ), indirectdiffuse( ), occlusion( ), transmission( ), and shadow( ). For example, trace( ) may be used in an expression as follows:RayOutputColor=trace(P,direction)When executing a trace( ) call, the renderer launches a ray from the shading point P in the specified direction. The parameters P and direction may also represent a list of origins or directions; in which case a single call to trace( ) may launch many rays, returning a list of results, or in some cases an averaged result. For each ray that intersects an object in the scene, a color value at a ray hit point (h) on the object is determined by executing a shader program associated with the hit object using h as the new shading point. The shader output value at the ray hit point is then returned to the shader program that launched the ray. For example, when a mirror (or some other type of reflective surface) is included in a scene, multiple rays are launched from the surface of the mirror. Whenever a ray intersects an object, a color value at the object hit point is returned to the surface of the mirror. The mirror surface is then colored with the color values returned from the rays such that a scene reflection is shown in the mirror. Sometimes, the shader program at the ray hit point may also call trace ( ), for example if that object is also reflective. Such nested ray tracing calls form what is referred to as a ray tree.
Ray trees are conventionally evaluated by tracing a first ray from a first launch point to a ray hit point on an object. A second ray is then traced from the ray hit point and the values returned by the second ray are used to compute the color value at the ray hit point. Given the color at the ray hit point, the first ray can return a value to the computation of the color value at the first launch point. The ray tree is evaluated in a depth first manner such that each ray is evaluated one at a time, one hit at a time. In other words, the shader program is evaluated at each hit point for each ray at the time of the hit on that point only. This method of evaluating shading along ray trees repeats many computational and data access operations which might be shared when many ray hits share the same shader program, thereby slowing the rendering process. Furthermore, when shading at the hit points involves further ray tracing, the method of shading one hit point at a time cannot take advantage of possible computational coherency that might arise out of tracing those additional rays as a group.
Therefore, what is needed is a method for evaluating ray trees that improves the performance of a ray tracing system.